/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2018年09月02日
*   描    述：
*   Copyright (C) 2018 All rights reserved.
*   
================================================================*/


#include <iostream>
#include <string>
using namespace std;


class Solution {
public:
    /**
     * @param A: A string
     * @param B: A string
     * @return: The length of longest common subsequence of A and B
     */
    int longestCommonSubsequence(string &A, string &B) {
        // write your code here
		int m = A.size();
        int n = B.size();
        if( m ==0 || n == 0 )
            return 0;

        int** lcs = new int*[m];
        for(int i = 0; i < m; i++)
            lcs[i] = new int[n];
        
        if( A[0] == B[0] )
            lcs[0][0] = 1;
        else
            lcs[0][0] = 0;

        for(int i = 1; i < m; i++)
            if( A[0] == B[i] )
                lcs[0][i] = 1;
            else
                lcs[0][i] = lcs[0][i-1];

        for(int j = 1; j < n; j++)
            if( A[j] == B[0] )
                lcs[j][0] = 1;
            else
                lcs[j][0] = lcs[j-1][0];
        
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if( A[i] == B[j] ){
                    lcs[i][j] = lcs[i-1][j-1] + 1;
                }else
                    lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);
            }
        }
        
        int result = lcs[m-1][n-1];
        for(int i = 0; i < m; i++)
            delete [] lcs[i];

        delete [] lcs;

        return result;
    }
};



